// https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/

// 算法思路总结：
// 1. 中序遍历将二叉搜索树转换为双向链表
// 2. 递归过程中维护前驱节点指针prev
// 3. 当前节点左指针指向前驱，前驱右指针指向当前
// 4. 最后连接首尾节点形成循环链表
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    void InorderConvert(TreeNode* cur, TreeNode*& prev)
    {
        if (cur == nullptr)
        {
            return ;
        }

        InorderConvert(cur->left, prev);

        cur->left = prev;
        if (prev != nullptr)
        {
            prev->right = cur;
        }
        prev = cur;

        InorderConvert(cur->right, prev);

        return ;
    }

    TreeNode* treeToDoublyList(TreeNode* root) 
    {
        if (root == nullptr)
        {
            return nullptr;
        }

        TreeNode* left, *cur = root;
        while (cur->left != nullptr)
        {
            cur = cur->left;
        }
        left = cur;

        TreeNode* prev = nullptr;
        InorderConvert(root, prev);

        left->left = prev;
        prev->right = left;
        
        return left;
    }
};

int main()
{
    vector<string> tree1 = {"4","2","5","1","3"};
    vector<string> tree2 = {"2","1","3"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << (sol.treeToDoublyList(root1)->val) << endl;
    cout << (sol.treeToDoublyList(root2)->val) << endl;

    return 0;
}